package com.yh;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class count {
	//堆调整：建最小堆；
	public static void HeapAdjust(Map.Entry[] Array,int beginIndex,int endIndex, int index)
	{
		int length = endIndex - beginIndex + 1;
		int largestIndex = index;
		int leftIndex = 2 * index + 1;     //下标从0开始，可以自己做实验
		int rightIndex = 2 * index + 2;
		//先找出子节点最大的数，array[i],array[2i+1],array[2i+2]的最大值
		if (leftIndex <= length - 1 && ((Integer)Array[leftIndex].getValue()) < ((Integer)Array[largestIndex].getValue()))//左边的子节点的值大，交换
		{
			largestIndex = leftIndex;
		} 
		if (rightIndex <= length - 1 && ((Integer)Array[rightIndex].getValue()) < ((Integer)Array[largestIndex].getValue()) )
		{
			largestIndex = rightIndex;
		}
		if (largestIndex != index) //如果array[i]不是最大的，交换array[i]与array[largeindex]
		{
			Map.Entry temp = Array [largestIndex];
			Array [largestIndex] = Array [index];
			Array [index] = temp;
			HeapAdjust (Array, beginIndex, endIndex, largestIndex);   //如此，再调整array[largeindex],但是值为array[index]
		}
	}
	//建堆
	public static void HeapBuild (Map.Entry[] Array )
	{
		for (int i = Array.length/2 -1; i >= 0; i --)
		{
			HeapAdjust (Array, 0, Array.length - 1, i);
		}
	}
	public static  void cw(String str, int k)
	{
		String array[] = str.split(";");
		HashMap <String, Integer> map = new HashMap <String,Integer>();
		Map.Entry heap[] = new Map.Entry[k];     //heap[]数组的每一个元素的类型都是Map.Entry，key-value;
		for (String ss : array)   
		{ 
			if (map.containsKey(ss))   
				map.put(ss,map.get(ss) + 1);   
				else   
					map.put(ss, 1); 
		} 
		int max = -1;
		String maxWord = null;
		int count = 0;
		for (Iterator iter = map.entrySet().iterator();iter.hasNext();) 
		{
			 Map.Entry entry = (Map.Entry) iter.next();
			 if (count < k - 1)
				 heap[count ++] = entry;
			 else
				 if (count == k - 1)
					 {
					 	heap[count ++] = entry;
					 	HeapBuild(heap);
					 }
				 else
				 {
					 Integer val = (Integer)entry.getValue();
					 if (val > (Integer)heap[0].getValue())
					 {
						 heap[0] = entry;
						 HeapAdjust (heap, 0, heap.length - 1, 0);
					 }
				 }
//	         String key = (String)entry.getKey();
//	         Integer val = (Integer)entry.getValue();
//	         System.out.print(key+" ");
//	         System.out.println(val);
//	         if (val > (Integer)max)
//	        	 {
//	        	 	max = val;
//	        	 	maxWord = key;
//	        	 }
	    }
		for (int i = 0; i < k; i++)
		{
			System.out.println(i+1 + ":" + "the word is : " + heap[i].getKey()+ "  its time is: " + heap[i].getValue());
		}
//		System.out.print("the max word is: " + maxWord + " and it appears " + max + " times");
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str = "ns;spring;到哪里_去;two;身材;five;flash;hard;nearby;Sunday;漂亮;walking;autumn;电脑;stop;shape;flash;pray;cool;漂亮;million;fish;much;March;south;south;sexy;outcome;never;cool;saas;summer;show;thousand;run;face;numbers;iaas;like;geometery;sound;when;season;Friday;520;sometime;throwing;iaas;she;airport;shape;818;two;perfectly;one;我爱你;battle;sometime;enough;war;arm;September;ferocious;weapons;stop;sometime;five;run;hide;incomplete;soldier;confused;January;stop;heart;cautious;miss;five;behind;outcome;cautious;wrong;month;season;run;respect;电脑;colder;arm;south;art;east;art;iaas;grey;love;winter;suspect;autumn;season;enough;hard;December;hide;818;throwing;three;February;hidden;电脑;airport;good;hero;我爱你;run;shine;wrong;outcome;numbers;nine;number;know;lead;azimuth;soldier;promise;colder;azimuth;nine;motor;view;confused;jack;dance;look;numbers;mean;play;weapons;turn;杯子;到哪里_去;believe;inside;sky;autumn;June;month;line;soldier;May;ten;night;free;incomplete;July;airport;我们;miss;may;nearby;feel;sexy;outcome;once;confused;rain;last;place;July;我爱你;sometime;azimuth;wrong;diamond;ferocious;cry;fish;miss;month;cost;enough;September;May;north;October;with;sword;sand;diamond;last;thousand;place;autumn;week;dance;mind;north;autumn;dance;four;thousand;sacred;may;July;with;nearby;love;down;much;matter;grey;cause;geometery;sexy;east;June;sexy;again;with;show;perfectly;free;night;company;battle;never;漂亮;battle;我爱你;spring;matter;mess;war;diamond;never;February;818;look;February;chance;she;书架destiny;heart;spring;incomplete;respect;weapons;seven;漂亮;fear;怡和祥云;August;iaas;hang;million;believe;day;face;blue;every;sand;south;shoulder;到哪里_去;cautious;beach;million;cost;grey;again;colder;battle;June;mind;saas;face;hero;hang;我们;September;show;summer;north;incomplete;weapons;battle;我爱你;much;break;sexy;way;five;Saturday;way;autumn;suspect;behind;cost;blue;walking;break;grey;sacred;behind;face;deep;cloud;thousand;hero;again;Friday;war;turn;Monday;when;colder;perfectly;手机;sword;chance;much;mind;漂亮;fear;look;line;sky;Monday;down;hide;run;line;perfectly;sky;lead;shine;lead;hang;beyond;January;sacred;paas;shine;November;may;电脑;hang;March;feel;sometime;answer;color;cry;mind;inside;cautious;autumn;sand;way;我爱你;stop;stop;million;flash;probable;number;find;ten;feel;手机;blue;我爱你;thousand;shoulder;two;lead;sometime;free;电脑;battle;last;four;520;good;March;beyond;battle;Friday;see;23;nine;cautious;23;love;beyond;sand;one;with;December;miss;cloud;war;October;soldier;thousand;我们;war;million;turn;again;line;deep;like;spring;love;south;run;soldier;winter;October;cool;color;free;way;good;turn;我们;spring;mean;much;six;Tuesday;face;我爱你;face;three;deep;four;mean;part;five;sound;loud;身材;inside;like;pray;shoulder;battle;hard;much;September;hidden;numbers;";
	    cw(str, 5);	
	}
}